class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        const int INF = 0x3f3f3f3f;
        int n = coins.size();
        //多开辟一行一列
        vector<vector<int>> dp(n+1,vector<int>(amount+1));
        //将第一行进行初始化，构不成的初始化为无效值INF
        for(int i =1;i<=amount;i++)
        {
            dp[0][i] = INF;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=amount;j++)
            {
                dp[i][j] = dp[i-1][j];
                if(j>=coins[i-1])
                    dp[i][j] = min(dp[i][j],dp[i][j-coins[i-1]]+1);
            }
        }
        return dp[n][amount] >=INF?-1:dp[n][amount];
    }
};
//滚动数组优化
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        const int INF = 0x3f3f3f3f;
        int n = coins.size();
        //多开辟一行一列
        vector<int>dp(amount+1,INF) ;
        dp[0] = 0;
        for(int i=1;i<=n;i++)
        {
            for(int j=coins[i-1];j<=amount;j++)
            {
                    dp[j] = min(dp[j],dp[j-coins[i-1]]+1);
            }
        }
        return dp[amount] >=INF?-1:dp[amount];
    }
};